Left Termination of the query pattern ss_in_2(a, g) w.r.t. the given Prolog program could not be shown:



↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof

Clauses:

ss(Xs, Ys) :- ','(perm(Xs, Ys), ordered(Ys)).
perm([], []).
perm(Xs, .(X, Ys)) :- ','(app(X1s, .(X, X2s), Xs), ','(app(X1s, X2s, Zs), perm(Zs, Ys))).
app([], X, X).
app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs).
ordered([]).
ordered(.(X, [])).
ordered(.(X, .(Y, Xs))) :- ','(less(X, s(Y)), ordered(.(Y, Xs))).
less(0, s(X)).
less(s(X), s(Y)) :- less(X, Y).

Queries:

ss(a,g).

We use the technique of [30]. With regard to the inferred argument filtering the predicates were used in the following modes:
ss_in: (f,b)
perm_in: (f,b) (f,f)
app_in: (f,b,f) (b,f,f) (f,f,f)
ordered_in: (b)
less_in: (f,b) (f,f)
Transforming Prolog into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1)

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
  ↳ PrologToPiTRSProof

Pi-finite rewrite system:
The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1)


Using Dependency Pairs [1,30] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

SS_IN_AG(Xs, Ys) → U1_AG(Xs, Ys, perm_in_ag(Xs, Ys))
SS_IN_AG(Xs, Ys) → PERM_IN_AG(Xs, Ys)
PERM_IN_AG(Xs, .(X, Ys)) → U3_AG(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
PERM_IN_AG(Xs, .(X, Ys)) → APP_IN_AGA(X1s, .(X, X2s), Xs)
APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → U6_AGA(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AGA(Xs, Ys, Zs)
U3_AG(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U3_AG(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → APP_IN_GAA(X1s, X2s, Zs)
APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) → U6_GAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)
APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → U6_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)
U4_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_AG(Xs, X, Ys, perm_in_aa(Zs, Ys))
U4_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
PERM_IN_AA(Xs, .(X, Ys)) → U3_AA(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
PERM_IN_AA(Xs, .(X, Ys)) → APP_IN_AGA(X1s, .(X, X2s), Xs)
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AA(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → APP_IN_GAA(X1s, X2s, Zs)
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_AA(Xs, X, Ys, perm_in_aa(Zs, Ys))
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
U1_AG(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_AG(Xs, Ys, ordered_in_g(Ys))
U1_AG(Xs, Ys, perm_out_ag(Xs, Ys)) → ORDERED_IN_G(Ys)
ORDERED_IN_G(.(X, .(Y, Xs))) → U7_G(X, Y, Xs, less_in_ag(X, s(Y)))
ORDERED_IN_G(.(X, .(Y, Xs))) → LESS_IN_AG(X, s(Y))
LESS_IN_AG(s(X), s(Y)) → U9_AG(X, Y, less_in_aa(X, Y))
LESS_IN_AG(s(X), s(Y)) → LESS_IN_AA(X, Y)
LESS_IN_AA(s(X), s(Y)) → U9_AA(X, Y, less_in_aa(X, Y))
LESS_IN_AA(s(X), s(Y)) → LESS_IN_AA(X, Y)
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → U8_G(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → ORDERED_IN_G(.(Y, Xs))

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1)
APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA
U5_AA(x1, x2, x3, x4)  =  U5_AA(x1, x4)
LESS_IN_AA(x1, x2)  =  LESS_IN_AA
U7_G(x1, x2, x3, x4)  =  U7_G(x4)
APP_IN_AGA(x1, x2, x3)  =  APP_IN_AGA(x2)
U6_AGA(x1, x2, x3, x4, x5)  =  U6_AGA(x5)
U6_GAA(x1, x2, x3, x4, x5)  =  U6_GAA(x5)
PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)
U3_AG(x1, x2, x3, x4)  =  U3_AG(x4)
U9_AG(x1, x2, x3)  =  U9_AG(x3)
U2_AG(x1, x2, x3)  =  U2_AG(x1, x3)
LESS_IN_AG(x1, x2)  =  LESS_IN_AG(x2)
U4_AA(x1, x2, x3, x4)  =  U4_AA(x1, x4)
ORDERED_IN_G(x1)  =  ORDERED_IN_G(x1)
U4_AG(x1, x2, x3, x4)  =  U4_AG(x1, x4)
U6_AAA(x1, x2, x3, x4, x5)  =  U6_AAA(x5)
U8_G(x1, x2, x3, x4)  =  U8_G(x4)
U9_AA(x1, x2, x3)  =  U9_AA(x3)
SS_IN_AG(x1, x2)  =  SS_IN_AG(x2)
U1_AG(x1, x2, x3)  =  U1_AG(x2, x3)
PERM_IN_AA(x1, x2)  =  PERM_IN_AA
APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)
U5_AG(x1, x2, x3, x4)  =  U5_AG(x1, x4)
U3_AA(x1, x2, x3, x4)  =  U3_AA(x4)

We have to consider all (P,R,Pi)-chains

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

SS_IN_AG(Xs, Ys) → U1_AG(Xs, Ys, perm_in_ag(Xs, Ys))
SS_IN_AG(Xs, Ys) → PERM_IN_AG(Xs, Ys)
PERM_IN_AG(Xs, .(X, Ys)) → U3_AG(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
PERM_IN_AG(Xs, .(X, Ys)) → APP_IN_AGA(X1s, .(X, X2s), Xs)
APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → U6_AGA(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AGA(Xs, Ys, Zs)
U3_AG(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U3_AG(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → APP_IN_GAA(X1s, X2s, Zs)
APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) → U6_GAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)
APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → U6_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)
U4_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_AG(Xs, X, Ys, perm_in_aa(Zs, Ys))
U4_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
PERM_IN_AA(Xs, .(X, Ys)) → U3_AA(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
PERM_IN_AA(Xs, .(X, Ys)) → APP_IN_AGA(X1s, .(X, X2s), Xs)
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AA(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → APP_IN_GAA(X1s, X2s, Zs)
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_AA(Xs, X, Ys, perm_in_aa(Zs, Ys))
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
U1_AG(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_AG(Xs, Ys, ordered_in_g(Ys))
U1_AG(Xs, Ys, perm_out_ag(Xs, Ys)) → ORDERED_IN_G(Ys)
ORDERED_IN_G(.(X, .(Y, Xs))) → U7_G(X, Y, Xs, less_in_ag(X, s(Y)))
ORDERED_IN_G(.(X, .(Y, Xs))) → LESS_IN_AG(X, s(Y))
LESS_IN_AG(s(X), s(Y)) → U9_AG(X, Y, less_in_aa(X, Y))
LESS_IN_AG(s(X), s(Y)) → LESS_IN_AA(X, Y)
LESS_IN_AA(s(X), s(Y)) → U9_AA(X, Y, less_in_aa(X, Y))
LESS_IN_AA(s(X), s(Y)) → LESS_IN_AA(X, Y)
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → U8_G(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → ORDERED_IN_G(.(Y, Xs))

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1)
APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA
U5_AA(x1, x2, x3, x4)  =  U5_AA(x1, x4)
LESS_IN_AA(x1, x2)  =  LESS_IN_AA
U7_G(x1, x2, x3, x4)  =  U7_G(x4)
APP_IN_AGA(x1, x2, x3)  =  APP_IN_AGA(x2)
U6_AGA(x1, x2, x3, x4, x5)  =  U6_AGA(x5)
U6_GAA(x1, x2, x3, x4, x5)  =  U6_GAA(x5)
PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)
U3_AG(x1, x2, x3, x4)  =  U3_AG(x4)
U9_AG(x1, x2, x3)  =  U9_AG(x3)
U2_AG(x1, x2, x3)  =  U2_AG(x1, x3)
LESS_IN_AG(x1, x2)  =  LESS_IN_AG(x2)
U4_AA(x1, x2, x3, x4)  =  U4_AA(x1, x4)
ORDERED_IN_G(x1)  =  ORDERED_IN_G(x1)
U4_AG(x1, x2, x3, x4)  =  U4_AG(x1, x4)
U6_AAA(x1, x2, x3, x4, x5)  =  U6_AAA(x5)
U8_G(x1, x2, x3, x4)  =  U8_G(x4)
U9_AA(x1, x2, x3)  =  U9_AA(x3)
SS_IN_AG(x1, x2)  =  SS_IN_AG(x2)
U1_AG(x1, x2, x3)  =  U1_AG(x2, x3)
PERM_IN_AA(x1, x2)  =  PERM_IN_AA
APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)
U5_AG(x1, x2, x3, x4)  =  U5_AG(x1, x4)
U3_AA(x1, x2, x3, x4)  =  U3_AA(x4)

We have to consider all (P,R,Pi)-chains
The approximation of the Dependency Graph [30] contains 5 SCCs with 22 less nodes.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

LESS_IN_AA(s(X), s(Y)) → LESS_IN_AA(X, Y)

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1)
LESS_IN_AA(x1, x2)  =  LESS_IN_AA

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

LESS_IN_AA(s(X), s(Y)) → LESS_IN_AA(X, Y)

R is empty.
The argument filtering Pi contains the following mapping:
s(x1)  =  s
LESS_IN_AA(x1, x2)  =  LESS_IN_AA

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ NonTerminationProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

LESS_IN_AA → LESS_IN_AA

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

The TRS P consists of the following rules:

LESS_IN_AA → LESS_IN_AA

The TRS R consists of the following rules:none


s = LESS_IN_AA evaluates to t =LESS_IN_AA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from LESS_IN_AA to LESS_IN_AA.





↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

ORDERED_IN_G(.(X, .(Y, Xs))) → U7_G(X, Y, Xs, less_in_ag(X, s(Y)))
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → ORDERED_IN_G(.(Y, Xs))

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1)
U7_G(x1, x2, x3, x4)  =  U7_G(x4)
ORDERED_IN_G(x1)  =  ORDERED_IN_G(x1)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

ORDERED_IN_G(.(X, .(Y, Xs))) → U7_G(X, Y, Xs, less_in_ag(X, s(Y)))
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → ORDERED_IN_G(.(Y, Xs))

The TRS R consists of the following rules:

less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U7_G(x1, x2, x3, x4)  =  U7_G(x4)
ORDERED_IN_G(x1)  =  ORDERED_IN_G(x1)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

U7_G(less_out_ag(X)) → ORDERED_IN_G(.)
ORDERED_IN_G(.) → U7_G(less_in_ag(s))

The TRS R consists of the following rules:

less_in_ag(s) → less_out_ag(0)
less_in_ag(s) → U9_ag(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s)
less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)

The set Q consists of the following terms:

less_in_ag(x0)
U9_ag(x0)
less_in_aa
U9_aa(x0)

We have to consider all (P,Q,R)-chains.
By narrowing [15] the rule ORDERED_IN_G(.) → U7_G(less_in_ag(s)) at position [0] we obtained the following new rules:

ORDERED_IN_G(.) → U7_G(less_out_ag(0))
ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

U7_G(less_out_ag(X)) → ORDERED_IN_G(.)
ORDERED_IN_G(.) → U7_G(less_out_ag(0))
ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))

The TRS R consists of the following rules:

less_in_ag(s) → less_out_ag(0)
less_in_ag(s) → U9_ag(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s)
less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)

The set Q consists of the following terms:

less_in_ag(x0)
U9_ag(x0)
less_in_aa
U9_aa(x0)

We have to consider all (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ UsableRulesProof
                              ↳ QDP
                                ↳ QReductionProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

U7_G(less_out_ag(X)) → ORDERED_IN_G(.)
ORDERED_IN_G(.) → U7_G(less_out_ag(0))
ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))

The TRS R consists of the following rules:

less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)

The set Q consists of the following terms:

less_in_ag(x0)
U9_ag(x0)
less_in_aa
U9_aa(x0)

We have to consider all (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

less_in_ag(x0)



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ UsableRulesProof
                              ↳ QDP
                                ↳ QReductionProof
                                  ↳ QDP
                                    ↳ NonTerminationProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

U7_G(less_out_ag(X)) → ORDERED_IN_G(.)
ORDERED_IN_G(.) → U7_G(less_out_ag(0))
ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))

The TRS R consists of the following rules:

less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)

The set Q consists of the following terms:

U9_ag(x0)
less_in_aa
U9_aa(x0)

We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by narrowing to the left:

The TRS P consists of the following rules:

U7_G(less_out_ag(X)) → ORDERED_IN_G(.)
ORDERED_IN_G(.) → U7_G(less_out_ag(0))
ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))

The TRS R consists of the following rules:

less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)


s = ORDERED_IN_G(.) evaluates to t =ORDERED_IN_G(.)

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

ORDERED_IN_G(.) → U7_G(less_out_ag(0))
with rule ORDERED_IN_G(.) → U7_G(less_out_ag(0)) at position [] and matcher [ ]

U7_G(less_out_ag(0)) → ORDERED_IN_G(.)
with rule U7_G(less_out_ag(X)) → ORDERED_IN_G(.)

Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence


All these steps are and every following step will be a correct step w.r.t to Q.





↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1)
APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .
APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ NonTerminationProof
              ↳ PiDP
              ↳ PiDP
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

APP_IN_AAA → APP_IN_AAA

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

The TRS P consists of the following rules:

APP_IN_AAA → APP_IN_AAA

The TRS R consists of the following rules:none


s = APP_IN_AAA evaluates to t =APP_IN_AAA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from APP_IN_AAA to APP_IN_AAA.





↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
              ↳ PiDP
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AGA(Xs, Ys, Zs)

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1)
APP_IN_AGA(x1, x2, x3)  =  APP_IN_AGA(x2)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AGA(Xs, Ys, Zs)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .
APP_IN_AGA(x1, x2, x3)  =  APP_IN_AGA(x2)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ NonTerminationProof
              ↳ PiDP
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

APP_IN_AGA(Ys) → APP_IN_AGA(Ys)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

The TRS P consists of the following rules:

APP_IN_AGA(Ys) → APP_IN_AGA(Ys)

The TRS R consists of the following rules:none


s = APP_IN_AGA(Ys) evaluates to t =APP_IN_AGA(Ys)

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from APP_IN_AGA(Ys) to APP_IN_AGA(Ys).





↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

PERM_IN_AA(Xs, .(X, Ys)) → U3_AA(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AA(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1)
U4_AA(x1, x2, x3, x4)  =  U4_AA(x1, x4)
PERM_IN_AA(x1, x2)  =  PERM_IN_AA
U3_AA(x1, x2, x3, x4)  =  U3_AA(x4)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
  ↳ PrologToPiTRSProof

Pi DP problem:
The TRS P consists of the following rules:

PERM_IN_AA(Xs, .(X, Ys)) → U3_AA(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AA(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))

The TRS R consists of the following rules:

app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))

The argument filtering Pi contains the following mapping:
[]  =  []
.(x1, x2)  =  .
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x5)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U4_AA(x1, x2, x3, x4)  =  U4_AA(x1, x4)
PERM_IN_AA(x1, x2)  =  PERM_IN_AA
U3_AA(x1, x2, x3, x4)  =  U3_AA(x4)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

U4_AA(Xs, app_out_gaa) → PERM_IN_AA
PERM_IN_AA → U3_AA(app_in_aga(.))
U3_AA(app_out_aga(X1s, Xs)) → U4_AA(Xs, app_in_gaa(X1s))

The TRS R consists of the following rules:

app_in_aga(X) → app_out_aga([], X)
app_in_aga(Ys) → U6_aga(app_in_aga(Ys))
app_in_gaa([]) → app_out_gaa
app_in_gaa(.) → U6_gaa(app_in_aaa)
U6_aga(app_out_aga(Xs, Zs)) → app_out_aga(., .)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa
app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)

The set Q consists of the following terms:

app_in_aga(x0)
app_in_gaa(x0)
U6_aga(x0)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
By narrowing [15] the rule PERM_IN_AA → U3_AA(app_in_aga(.)) at position [0] we obtained the following new rules:

PERM_IN_AA → U3_AA(U6_aga(app_in_aga(.)))
PERM_IN_AA → U3_AA(app_out_aga([], .))



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ Narrowing
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

PERM_IN_AA → U3_AA(U6_aga(app_in_aga(.)))
U4_AA(Xs, app_out_gaa) → PERM_IN_AA
U3_AA(app_out_aga(X1s, Xs)) → U4_AA(Xs, app_in_gaa(X1s))
PERM_IN_AA → U3_AA(app_out_aga([], .))

The TRS R consists of the following rules:

app_in_aga(X) → app_out_aga([], X)
app_in_aga(Ys) → U6_aga(app_in_aga(Ys))
app_in_gaa([]) → app_out_gaa
app_in_gaa(.) → U6_gaa(app_in_aaa)
U6_aga(app_out_aga(Xs, Zs)) → app_out_aga(., .)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa
app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)

The set Q consists of the following terms:

app_in_aga(x0)
app_in_gaa(x0)
U6_aga(x0)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
By narrowing [15] the rule U3_AA(app_out_aga(X1s, Xs)) → U4_AA(Xs, app_in_gaa(X1s)) at position [1] we obtained the following new rules:

U3_AA(app_out_aga([], y1)) → U4_AA(y1, app_out_gaa)
U3_AA(app_out_aga(., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ Narrowing
                              ↳ QDP
                                ↳ UsableRulesProof
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

PERM_IN_AA → U3_AA(U6_aga(app_in_aga(.)))
U4_AA(Xs, app_out_gaa) → PERM_IN_AA
U3_AA(app_out_aga([], y1)) → U4_AA(y1, app_out_gaa)
PERM_IN_AA → U3_AA(app_out_aga([], .))
U3_AA(app_out_aga(., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))

The TRS R consists of the following rules:

app_in_aga(X) → app_out_aga([], X)
app_in_aga(Ys) → U6_aga(app_in_aga(Ys))
app_in_gaa([]) → app_out_gaa
app_in_gaa(.) → U6_gaa(app_in_aaa)
U6_aga(app_out_aga(Xs, Zs)) → app_out_aga(., .)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa
app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)

The set Q consists of the following terms:

app_in_aga(x0)
app_in_gaa(x0)
U6_aga(x0)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ Narrowing
                              ↳ QDP
                                ↳ UsableRulesProof
                                  ↳ QDP
                                    ↳ QReductionProof
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

PERM_IN_AA → U3_AA(U6_aga(app_in_aga(.)))
U4_AA(Xs, app_out_gaa) → PERM_IN_AA
U3_AA(app_out_aga([], y1)) → U4_AA(y1, app_out_gaa)
PERM_IN_AA → U3_AA(app_out_aga([], .))
U3_AA(app_out_aga(., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))

The TRS R consists of the following rules:

app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)
app_in_aga(X) → app_out_aga([], X)
app_in_aga(Ys) → U6_aga(app_in_aga(Ys))
U6_aga(app_out_aga(Xs, Zs)) → app_out_aga(., .)

The set Q consists of the following terms:

app_in_aga(x0)
app_in_gaa(x0)
U6_aga(x0)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

app_in_gaa(x0)



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ Narrowing
                              ↳ QDP
                                ↳ UsableRulesProof
                                  ↳ QDP
                                    ↳ QReductionProof
                                      ↳ QDP
                                        ↳ NonTerminationProof
  ↳ PrologToPiTRSProof

Q DP problem:
The TRS P consists of the following rules:

PERM_IN_AA → U3_AA(U6_aga(app_in_aga(.)))
U4_AA(Xs, app_out_gaa) → PERM_IN_AA
U3_AA(app_out_aga([], y1)) → U4_AA(y1, app_out_gaa)
PERM_IN_AA → U3_AA(app_out_aga([], .))
U3_AA(app_out_aga(., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))

The TRS R consists of the following rules:

app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)
app_in_aga(X) → app_out_aga([], X)
app_in_aga(Ys) → U6_aga(app_in_aga(Ys))
U6_aga(app_out_aga(Xs, Zs)) → app_out_aga(., .)

The set Q consists of the following terms:

app_in_aga(x0)
U6_aga(x0)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by narrowing to the left:

The TRS P consists of the following rules:

PERM_IN_AA → U3_AA(U6_aga(app_in_aga(.)))
U4_AA(Xs, app_out_gaa) → PERM_IN_AA
U3_AA(app_out_aga([], y1)) → U4_AA(y1, app_out_gaa)
PERM_IN_AA → U3_AA(app_out_aga([], .))
U3_AA(app_out_aga(., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))

The TRS R consists of the following rules:

app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)
app_in_aga(X) → app_out_aga([], X)
app_in_aga(Ys) → U6_aga(app_in_aga(Ys))
U6_aga(app_out_aga(Xs, Zs)) → app_out_aga(., .)


s = PERM_IN_AA evaluates to t =PERM_IN_AA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

PERM_IN_AA → U3_AA(app_out_aga([], .))
with rule PERM_IN_AA → U3_AA(app_out_aga([], .)) at position [] and matcher [ ]

U3_AA(app_out_aga([], .)) → U4_AA(., app_out_gaa)
with rule U3_AA(app_out_aga([], y1)) → U4_AA(y1, app_out_gaa) at position [] and matcher [y1 / .]

U4_AA(., app_out_gaa) → PERM_IN_AA
with rule U4_AA(Xs, app_out_gaa) → PERM_IN_AA

Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence


All these steps are and every following step will be a correct step w.r.t to Q.




We use the technique of [30]. With regard to the inferred argument filtering the predicates were used in the following modes:
ss_in: (f,b)
perm_in: (f,b) (f,f)
app_in: (f,b,f) (b,f,f) (f,f,f)
ordered_in: (b)
less_in: (f,b) (f,f)
Transforming Prolog into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1, x2)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x2, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g(x1)
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1, x2)

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog



↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof

Pi-finite rewrite system:
The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1, x2)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x2, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g(x1)
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1, x2)


Using Dependency Pairs [1,30] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

SS_IN_AG(Xs, Ys) → U1_AG(Xs, Ys, perm_in_ag(Xs, Ys))
SS_IN_AG(Xs, Ys) → PERM_IN_AG(Xs, Ys)
PERM_IN_AG(Xs, .(X, Ys)) → U3_AG(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
PERM_IN_AG(Xs, .(X, Ys)) → APP_IN_AGA(X1s, .(X, X2s), Xs)
APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → U6_AGA(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AGA(Xs, Ys, Zs)
U3_AG(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U3_AG(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → APP_IN_GAA(X1s, X2s, Zs)
APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) → U6_GAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)
APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → U6_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)
U4_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_AG(Xs, X, Ys, perm_in_aa(Zs, Ys))
U4_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
PERM_IN_AA(Xs, .(X, Ys)) → U3_AA(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
PERM_IN_AA(Xs, .(X, Ys)) → APP_IN_AGA(X1s, .(X, X2s), Xs)
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AA(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → APP_IN_GAA(X1s, X2s, Zs)
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_AA(Xs, X, Ys, perm_in_aa(Zs, Ys))
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
U1_AG(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_AG(Xs, Ys, ordered_in_g(Ys))
U1_AG(Xs, Ys, perm_out_ag(Xs, Ys)) → ORDERED_IN_G(Ys)
ORDERED_IN_G(.(X, .(Y, Xs))) → U7_G(X, Y, Xs, less_in_ag(X, s(Y)))
ORDERED_IN_G(.(X, .(Y, Xs))) → LESS_IN_AG(X, s(Y))
LESS_IN_AG(s(X), s(Y)) → U9_AG(X, Y, less_in_aa(X, Y))
LESS_IN_AG(s(X), s(Y)) → LESS_IN_AA(X, Y)
LESS_IN_AA(s(X), s(Y)) → U9_AA(X, Y, less_in_aa(X, Y))
LESS_IN_AA(s(X), s(Y)) → LESS_IN_AA(X, Y)
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → U8_G(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → ORDERED_IN_G(.(Y, Xs))

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1, x2)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x2, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g(x1)
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1, x2)
APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA
U5_AA(x1, x2, x3, x4)  =  U5_AA(x1, x4)
LESS_IN_AA(x1, x2)  =  LESS_IN_AA
U7_G(x1, x2, x3, x4)  =  U7_G(x4)
APP_IN_AGA(x1, x2, x3)  =  APP_IN_AGA(x2)
U6_AGA(x1, x2, x3, x4, x5)  =  U6_AGA(x3, x5)
U6_GAA(x1, x2, x3, x4, x5)  =  U6_GAA(x5)
PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)
U3_AG(x1, x2, x3, x4)  =  U3_AG(x4)
U9_AG(x1, x2, x3)  =  U9_AG(x3)
U2_AG(x1, x2, x3)  =  U2_AG(x1, x2, x3)
LESS_IN_AG(x1, x2)  =  LESS_IN_AG(x2)
U4_AA(x1, x2, x3, x4)  =  U4_AA(x1, x4)
ORDERED_IN_G(x1)  =  ORDERED_IN_G(x1)
U4_AG(x1, x2, x3, x4)  =  U4_AG(x1, x4)
U6_AAA(x1, x2, x3, x4, x5)  =  U6_AAA(x5)
U8_G(x1, x2, x3, x4)  =  U8_G(x4)
U9_AA(x1, x2, x3)  =  U9_AA(x3)
SS_IN_AG(x1, x2)  =  SS_IN_AG(x2)
U1_AG(x1, x2, x3)  =  U1_AG(x2, x3)
PERM_IN_AA(x1, x2)  =  PERM_IN_AA
APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)
U5_AG(x1, x2, x3, x4)  =  U5_AG(x1, x4)
U3_AA(x1, x2, x3, x4)  =  U3_AA(x4)

We have to consider all (P,R,Pi)-chains

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof

Pi DP problem:
The TRS P consists of the following rules:

SS_IN_AG(Xs, Ys) → U1_AG(Xs, Ys, perm_in_ag(Xs, Ys))
SS_IN_AG(Xs, Ys) → PERM_IN_AG(Xs, Ys)
PERM_IN_AG(Xs, .(X, Ys)) → U3_AG(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
PERM_IN_AG(Xs, .(X, Ys)) → APP_IN_AGA(X1s, .(X, X2s), Xs)
APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → U6_AGA(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AGA(Xs, Ys, Zs)
U3_AG(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U3_AG(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → APP_IN_GAA(X1s, X2s, Zs)
APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) → U6_GAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)
APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → U6_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)
U4_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_AG(Xs, X, Ys, perm_in_aa(Zs, Ys))
U4_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
PERM_IN_AA(Xs, .(X, Ys)) → U3_AA(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
PERM_IN_AA(Xs, .(X, Ys)) → APP_IN_AGA(X1s, .(X, X2s), Xs)
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AA(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → APP_IN_GAA(X1s, X2s, Zs)
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_AA(Xs, X, Ys, perm_in_aa(Zs, Ys))
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
U1_AG(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_AG(Xs, Ys, ordered_in_g(Ys))
U1_AG(Xs, Ys, perm_out_ag(Xs, Ys)) → ORDERED_IN_G(Ys)
ORDERED_IN_G(.(X, .(Y, Xs))) → U7_G(X, Y, Xs, less_in_ag(X, s(Y)))
ORDERED_IN_G(.(X, .(Y, Xs))) → LESS_IN_AG(X, s(Y))
LESS_IN_AG(s(X), s(Y)) → U9_AG(X, Y, less_in_aa(X, Y))
LESS_IN_AG(s(X), s(Y)) → LESS_IN_AA(X, Y)
LESS_IN_AA(s(X), s(Y)) → U9_AA(X, Y, less_in_aa(X, Y))
LESS_IN_AA(s(X), s(Y)) → LESS_IN_AA(X, Y)
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → U8_G(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → ORDERED_IN_G(.(Y, Xs))

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1, x2)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x2, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g(x1)
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1, x2)
APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA
U5_AA(x1, x2, x3, x4)  =  U5_AA(x1, x4)
LESS_IN_AA(x1, x2)  =  LESS_IN_AA
U7_G(x1, x2, x3, x4)  =  U7_G(x4)
APP_IN_AGA(x1, x2, x3)  =  APP_IN_AGA(x2)
U6_AGA(x1, x2, x3, x4, x5)  =  U6_AGA(x3, x5)
U6_GAA(x1, x2, x3, x4, x5)  =  U6_GAA(x5)
PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)
U3_AG(x1, x2, x3, x4)  =  U3_AG(x4)
U9_AG(x1, x2, x3)  =  U9_AG(x3)
U2_AG(x1, x2, x3)  =  U2_AG(x1, x2, x3)
LESS_IN_AG(x1, x2)  =  LESS_IN_AG(x2)
U4_AA(x1, x2, x3, x4)  =  U4_AA(x1, x4)
ORDERED_IN_G(x1)  =  ORDERED_IN_G(x1)
U4_AG(x1, x2, x3, x4)  =  U4_AG(x1, x4)
U6_AAA(x1, x2, x3, x4, x5)  =  U6_AAA(x5)
U8_G(x1, x2, x3, x4)  =  U8_G(x4)
U9_AA(x1, x2, x3)  =  U9_AA(x3)
SS_IN_AG(x1, x2)  =  SS_IN_AG(x2)
U1_AG(x1, x2, x3)  =  U1_AG(x2, x3)
PERM_IN_AA(x1, x2)  =  PERM_IN_AA
APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)
U5_AG(x1, x2, x3, x4)  =  U5_AG(x1, x4)
U3_AA(x1, x2, x3, x4)  =  U3_AA(x4)

We have to consider all (P,R,Pi)-chains
The approximation of the Dependency Graph [30] contains 5 SCCs with 22 less nodes.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

LESS_IN_AA(s(X), s(Y)) → LESS_IN_AA(X, Y)

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1, x2)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x2, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g(x1)
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1, x2)
LESS_IN_AA(x1, x2)  =  LESS_IN_AA

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

LESS_IN_AA(s(X), s(Y)) → LESS_IN_AA(X, Y)

R is empty.
The argument filtering Pi contains the following mapping:
s(x1)  =  s
LESS_IN_AA(x1, x2)  =  LESS_IN_AA

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ NonTerminationProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

LESS_IN_AA → LESS_IN_AA

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

The TRS P consists of the following rules:

LESS_IN_AA → LESS_IN_AA

The TRS R consists of the following rules:none


s = LESS_IN_AA evaluates to t =LESS_IN_AA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from LESS_IN_AA to LESS_IN_AA.





↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

ORDERED_IN_G(.(X, .(Y, Xs))) → U7_G(X, Y, Xs, less_in_ag(X, s(Y)))
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → ORDERED_IN_G(.(Y, Xs))

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1, x2)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x2, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g(x1)
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1, x2)
U7_G(x1, x2, x3, x4)  =  U7_G(x4)
ORDERED_IN_G(x1)  =  ORDERED_IN_G(x1)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

ORDERED_IN_G(.(X, .(Y, Xs))) → U7_G(X, Y, Xs, less_in_ag(X, s(Y)))
U7_G(X, Y, Xs, less_out_ag(X, s(Y))) → ORDERED_IN_G(.(Y, Xs))

The TRS R consists of the following rules:

less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U7_G(x1, x2, x3, x4)  =  U7_G(x4)
ORDERED_IN_G(x1)  =  ORDERED_IN_G(x1)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

ORDERED_IN_G(.) → U7_G(less_in_ag(s))
U7_G(less_out_ag(X, s)) → ORDERED_IN_G(.)

The TRS R consists of the following rules:

less_in_ag(s) → less_out_ag(0, s)
less_in_ag(s) → U9_ag(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s, s)
less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)

The set Q consists of the following terms:

less_in_ag(x0)
U9_ag(x0)
less_in_aa
U9_aa(x0)

We have to consider all (P,Q,R)-chains.
By narrowing [15] the rule ORDERED_IN_G(.) → U7_G(less_in_ag(s)) at position [0] we obtained the following new rules:

ORDERED_IN_G(.) → U7_G(less_out_ag(0, s))
ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))



↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))
ORDERED_IN_G(.) → U7_G(less_out_ag(0, s))
U7_G(less_out_ag(X, s)) → ORDERED_IN_G(.)

The TRS R consists of the following rules:

less_in_ag(s) → less_out_ag(0, s)
less_in_ag(s) → U9_ag(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s, s)
less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)

The set Q consists of the following terms:

less_in_ag(x0)
U9_ag(x0)
less_in_aa
U9_aa(x0)

We have to consider all (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ UsableRulesProof
                              ↳ QDP
                                ↳ QReductionProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))
ORDERED_IN_G(.) → U7_G(less_out_ag(0, s))
U7_G(less_out_ag(X, s)) → ORDERED_IN_G(.)

The TRS R consists of the following rules:

less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s, s)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)

The set Q consists of the following terms:

less_in_ag(x0)
U9_ag(x0)
less_in_aa
U9_aa(x0)

We have to consider all (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

less_in_ag(x0)



↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ UsableRulesProof
                              ↳ QDP
                                ↳ QReductionProof
                                  ↳ QDP
                                    ↳ NonTerminationProof
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))
ORDERED_IN_G(.) → U7_G(less_out_ag(0, s))
U7_G(less_out_ag(X, s)) → ORDERED_IN_G(.)

The TRS R consists of the following rules:

less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s, s)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)

The set Q consists of the following terms:

U9_ag(x0)
less_in_aa
U9_aa(x0)

We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by narrowing to the left:

The TRS P consists of the following rules:

ORDERED_IN_G(.) → U7_G(U9_ag(less_in_aa))
ORDERED_IN_G(.) → U7_G(less_out_ag(0, s))
U7_G(less_out_ag(X, s)) → ORDERED_IN_G(.)

The TRS R consists of the following rules:

less_in_aa → less_out_aa(0, s)
less_in_aa → U9_aa(less_in_aa)
U9_ag(less_out_aa(X, Y)) → less_out_ag(s, s)
U9_aa(less_out_aa(X, Y)) → less_out_aa(s, s)


s = U7_G(less_out_ag(X, s)) evaluates to t =U7_G(less_out_ag(0, s))

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

U7_G(less_out_ag(X, s)) → ORDERED_IN_G(.)
with rule U7_G(less_out_ag(X', s)) → ORDERED_IN_G(.) at position [] and matcher [X' / X]

ORDERED_IN_G(.) → U7_G(less_out_ag(0, s))
with rule ORDERED_IN_G(.) → U7_G(less_out_ag(0, s))

Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence


All these steps are and every following step will be a correct step w.r.t to Q.





↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1, x2)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x2, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g(x1)
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1, x2)
APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AAA(Xs, Ys, Zs)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .
APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ NonTerminationProof
              ↳ PiDP
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

APP_IN_AAA → APP_IN_AAA

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

The TRS P consists of the following rules:

APP_IN_AAA → APP_IN_AAA

The TRS R consists of the following rules:none


s = APP_IN_AAA evaluates to t =APP_IN_AAA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from APP_IN_AAA to APP_IN_AAA.





↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AGA(Xs, Ys, Zs)

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1, x2)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x2, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g(x1)
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1, x2)
APP_IN_AGA(x1, x2, x3)  =  APP_IN_AGA(x2)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

APP_IN_AGA(.(X, Xs), Ys, .(X, Zs)) → APP_IN_AGA(Xs, Ys, Zs)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .
APP_IN_AGA(x1, x2, x3)  =  APP_IN_AGA(x2)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ NonTerminationProof
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

APP_IN_AGA(Ys) → APP_IN_AGA(Ys)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

The TRS P consists of the following rules:

APP_IN_AGA(Ys) → APP_IN_AGA(Ys)

The TRS R consists of the following rules:none


s = APP_IN_AGA(Ys) evaluates to t =APP_IN_AGA(Ys)

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from APP_IN_AGA(Ys) to APP_IN_AGA(Ys).





↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof

Pi DP problem:
The TRS P consists of the following rules:

PERM_IN_AA(Xs, .(X, Ys)) → U3_AA(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AA(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))

The TRS R consists of the following rules:

ss_in_ag(Xs, Ys) → U1_ag(Xs, Ys, perm_in_ag(Xs, Ys))
perm_in_ag([], []) → perm_out_ag([], [])
perm_in_ag(Xs, .(X, Ys)) → U3_ag(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U3_ag(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
U4_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_ag(Xs, X, Ys, perm_in_aa(Zs, Ys))
perm_in_aa([], []) → perm_out_aa([], [])
perm_in_aa(Xs, .(X, Ys)) → U3_aa(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U3_aa(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_aa(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
U4_aa(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → U5_aa(Xs, X, Ys, perm_in_aa(Zs, Ys))
U5_aa(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_aa(Xs, .(X, Ys))
U5_ag(Xs, X, Ys, perm_out_aa(Zs, Ys)) → perm_out_ag(Xs, .(X, Ys))
U1_ag(Xs, Ys, perm_out_ag(Xs, Ys)) → U2_ag(Xs, Ys, ordered_in_g(Ys))
ordered_in_g([]) → ordered_out_g([])
ordered_in_g(.(X, [])) → ordered_out_g(.(X, []))
ordered_in_g(.(X, .(Y, Xs))) → U7_g(X, Y, Xs, less_in_ag(X, s(Y)))
less_in_ag(0, s(X)) → less_out_ag(0, s(X))
less_in_ag(s(X), s(Y)) → U9_ag(X, Y, less_in_aa(X, Y))
less_in_aa(0, s(X)) → less_out_aa(0, s(X))
less_in_aa(s(X), s(Y)) → U9_aa(X, Y, less_in_aa(X, Y))
U9_aa(X, Y, less_out_aa(X, Y)) → less_out_aa(s(X), s(Y))
U9_ag(X, Y, less_out_aa(X, Y)) → less_out_ag(s(X), s(Y))
U7_g(X, Y, Xs, less_out_ag(X, s(Y))) → U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs)))
U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) → ordered_out_g(.(X, .(Y, Xs)))
U2_ag(Xs, Ys, ordered_out_g(Ys)) → ss_out_ag(Xs, Ys)

The argument filtering Pi contains the following mapping:
ss_in_ag(x1, x2)  =  ss_in_ag(x2)
U1_ag(x1, x2, x3)  =  U1_ag(x2, x3)
perm_in_ag(x1, x2)  =  perm_in_ag(x2)
[]  =  []
perm_out_ag(x1, x2)  =  perm_out_ag(x1, x2)
.(x1, x2)  =  .
U3_ag(x1, x2, x3, x4)  =  U3_ag(x4)
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
U4_ag(x1, x2, x3, x4)  =  U4_ag(x1, x4)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U5_ag(x1, x2, x3, x4)  =  U5_ag(x1, x4)
perm_in_aa(x1, x2)  =  perm_in_aa
perm_out_aa(x1, x2)  =  perm_out_aa(x1, x2)
U3_aa(x1, x2, x3, x4)  =  U3_aa(x4)
U4_aa(x1, x2, x3, x4)  =  U4_aa(x1, x4)
U5_aa(x1, x2, x3, x4)  =  U5_aa(x1, x4)
U2_ag(x1, x2, x3)  =  U2_ag(x1, x2, x3)
ordered_in_g(x1)  =  ordered_in_g(x1)
ordered_out_g(x1)  =  ordered_out_g(x1)
U7_g(x1, x2, x3, x4)  =  U7_g(x4)
less_in_ag(x1, x2)  =  less_in_ag(x2)
s(x1)  =  s
less_out_ag(x1, x2)  =  less_out_ag(x1, x2)
U9_ag(x1, x2, x3)  =  U9_ag(x3)
less_in_aa(x1, x2)  =  less_in_aa
less_out_aa(x1, x2)  =  less_out_aa(x1, x2)
U9_aa(x1, x2, x3)  =  U9_aa(x3)
U8_g(x1, x2, x3, x4)  =  U8_g(x4)
ss_out_ag(x1, x2)  =  ss_out_ag(x1, x2)
U4_AA(x1, x2, x3, x4)  =  U4_AA(x1, x4)
PERM_IN_AA(x1, x2)  =  PERM_IN_AA
U3_AA(x1, x2, x3, x4)  =  U3_AA(x4)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof

Pi DP problem:
The TRS P consists of the following rules:

PERM_IN_AA(Xs, .(X, Ys)) → U3_AA(Xs, X, Ys, app_in_aga(X1s, .(X, X2s), Xs))
U4_AA(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) → PERM_IN_AA(Zs, Ys)
U3_AA(Xs, X, Ys, app_out_aga(X1s, .(X, X2s), Xs)) → U4_AA(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))

The TRS R consists of the following rules:

app_in_aga([], X, X) → app_out_aga([], X, X)
app_in_aga(.(X, Xs), Ys, .(X, Zs)) → U6_aga(X, Xs, Ys, Zs, app_in_aga(Xs, Ys, Zs))
app_in_gaa([], X, X) → app_out_gaa([], X, X)
app_in_gaa(.(X, Xs), Ys, .(X, Zs)) → U6_gaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aga(X, Xs, Ys, Zs, app_out_aga(Xs, Ys, Zs)) → app_out_aga(.(X, Xs), Ys, .(X, Zs))
U6_gaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_gaa(.(X, Xs), Ys, .(X, Zs))
app_in_aaa([], X, X) → app_out_aaa([], X, X)
app_in_aaa(.(X, Xs), Ys, .(X, Zs)) → U6_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
U6_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) → app_out_aaa(.(X, Xs), Ys, .(X, Zs))

The argument filtering Pi contains the following mapping:
[]  =  []
.(x1, x2)  =  .
app_in_aga(x1, x2, x3)  =  app_in_aga(x2)
app_out_aga(x1, x2, x3)  =  app_out_aga(x1, x2, x3)
U6_aga(x1, x2, x3, x4, x5)  =  U6_aga(x3, x5)
app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)
app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)
U6_gaa(x1, x2, x3, x4, x5)  =  U6_gaa(x5)
app_in_aaa(x1, x2, x3)  =  app_in_aaa
app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)
U6_aaa(x1, x2, x3, x4, x5)  =  U6_aaa(x5)
U4_AA(x1, x2, x3, x4)  =  U4_AA(x1, x4)
PERM_IN_AA(x1, x2)  =  PERM_IN_AA
U3_AA(x1, x2, x3, x4)  =  U3_AA(x4)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing

Q DP problem:
The TRS P consists of the following rules:

U4_AA(Xs, app_out_gaa(X1s)) → PERM_IN_AA
PERM_IN_AA → U3_AA(app_in_aga(.))
U3_AA(app_out_aga(X1s, ., Xs)) → U4_AA(Xs, app_in_gaa(X1s))

The TRS R consists of the following rules:

app_in_aga(X) → app_out_aga([], X, X)
app_in_aga(Ys) → U6_aga(Ys, app_in_aga(Ys))
app_in_gaa([]) → app_out_gaa([])
app_in_gaa(.) → U6_gaa(app_in_aaa)
U6_aga(Ys, app_out_aga(Xs, Ys, Zs)) → app_out_aga(., Ys, .)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa(.)
app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)

The set Q consists of the following terms:

app_in_aga(x0)
app_in_gaa(x0)
U6_aga(x0, x1)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
By narrowing [15] the rule PERM_IN_AA → U3_AA(app_in_aga(.)) at position [0] we obtained the following new rules:

PERM_IN_AA → U3_AA(app_out_aga([], ., .))
PERM_IN_AA → U3_AA(U6_aga(., app_in_aga(.)))



↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ Narrowing

Q DP problem:
The TRS P consists of the following rules:

PERM_IN_AA → U3_AA(app_out_aga([], ., .))
U4_AA(Xs, app_out_gaa(X1s)) → PERM_IN_AA
PERM_IN_AA → U3_AA(U6_aga(., app_in_aga(.)))
U3_AA(app_out_aga(X1s, ., Xs)) → U4_AA(Xs, app_in_gaa(X1s))

The TRS R consists of the following rules:

app_in_aga(X) → app_out_aga([], X, X)
app_in_aga(Ys) → U6_aga(Ys, app_in_aga(Ys))
app_in_gaa([]) → app_out_gaa([])
app_in_gaa(.) → U6_gaa(app_in_aaa)
U6_aga(Ys, app_out_aga(Xs, Ys, Zs)) → app_out_aga(., Ys, .)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa(.)
app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)

The set Q consists of the following terms:

app_in_aga(x0)
app_in_gaa(x0)
U6_aga(x0, x1)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
By narrowing [15] the rule U3_AA(app_out_aga(X1s, ., Xs)) → U4_AA(Xs, app_in_gaa(X1s)) at position [1] we obtained the following new rules:

U3_AA(app_out_aga([], ., y1)) → U4_AA(y1, app_out_gaa([]))
U3_AA(app_out_aga(., ., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))



↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ Narrowing
                              ↳ QDP
                                ↳ UsableRulesProof

Q DP problem:
The TRS P consists of the following rules:

U3_AA(app_out_aga([], ., y1)) → U4_AA(y1, app_out_gaa([]))
PERM_IN_AA → U3_AA(app_out_aga([], ., .))
U4_AA(Xs, app_out_gaa(X1s)) → PERM_IN_AA
PERM_IN_AA → U3_AA(U6_aga(., app_in_aga(.)))
U3_AA(app_out_aga(., ., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))

The TRS R consists of the following rules:

app_in_aga(X) → app_out_aga([], X, X)
app_in_aga(Ys) → U6_aga(Ys, app_in_aga(Ys))
app_in_gaa([]) → app_out_gaa([])
app_in_gaa(.) → U6_gaa(app_in_aaa)
U6_aga(Ys, app_out_aga(Xs, Ys, Zs)) → app_out_aga(., Ys, .)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa(.)
app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)

The set Q consists of the following terms:

app_in_aga(x0)
app_in_gaa(x0)
U6_aga(x0, x1)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.

↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ Narrowing
                              ↳ QDP
                                ↳ UsableRulesProof
                                  ↳ QDP
                                    ↳ QReductionProof

Q DP problem:
The TRS P consists of the following rules:

U3_AA(app_out_aga([], ., y1)) → U4_AA(y1, app_out_gaa([]))
PERM_IN_AA → U3_AA(app_out_aga([], ., .))
U4_AA(Xs, app_out_gaa(X1s)) → PERM_IN_AA
PERM_IN_AA → U3_AA(U6_aga(., app_in_aga(.)))
U3_AA(app_out_aga(., ., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))

The TRS R consists of the following rules:

app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa(.)
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)
app_in_aga(X) → app_out_aga([], X, X)
app_in_aga(Ys) → U6_aga(Ys, app_in_aga(Ys))
U6_aga(Ys, app_out_aga(Xs, Ys, Zs)) → app_out_aga(., Ys, .)

The set Q consists of the following terms:

app_in_aga(x0)
app_in_gaa(x0)
U6_aga(x0, x1)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

app_in_gaa(x0)



↳ Prolog
  ↳ PrologToPiTRSProof
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
                      ↳ QDP
                        ↳ Narrowing
                          ↳ QDP
                            ↳ Narrowing
                              ↳ QDP
                                ↳ UsableRulesProof
                                  ↳ QDP
                                    ↳ QReductionProof
                                      ↳ QDP
                                        ↳ NonTerminationProof

Q DP problem:
The TRS P consists of the following rules:

U3_AA(app_out_aga([], ., y1)) → U4_AA(y1, app_out_gaa([]))
PERM_IN_AA → U3_AA(app_out_aga([], ., .))
U4_AA(Xs, app_out_gaa(X1s)) → PERM_IN_AA
PERM_IN_AA → U3_AA(U6_aga(., app_in_aga(.)))
U3_AA(app_out_aga(., ., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))

The TRS R consists of the following rules:

app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa(.)
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)
app_in_aga(X) → app_out_aga([], X, X)
app_in_aga(Ys) → U6_aga(Ys, app_in_aga(Ys))
U6_aga(Ys, app_out_aga(Xs, Ys, Zs)) → app_out_aga(., Ys, .)

The set Q consists of the following terms:

app_in_aga(x0)
U6_aga(x0, x1)
U6_gaa(x0)
app_in_aaa
U6_aaa(x0)

We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by narrowing to the left:

The TRS P consists of the following rules:

U3_AA(app_out_aga([], ., y1)) → U4_AA(y1, app_out_gaa([]))
PERM_IN_AA → U3_AA(app_out_aga([], ., .))
U4_AA(Xs, app_out_gaa(X1s)) → PERM_IN_AA
PERM_IN_AA → U3_AA(U6_aga(., app_in_aga(.)))
U3_AA(app_out_aga(., ., y1)) → U4_AA(y1, U6_gaa(app_in_aaa))

The TRS R consists of the following rules:

app_in_aaa → app_out_aaa([])
app_in_aaa → U6_aaa(app_in_aaa)
U6_gaa(app_out_aaa(Xs)) → app_out_gaa(.)
U6_aaa(app_out_aaa(Xs)) → app_out_aaa(.)
app_in_aga(X) → app_out_aga([], X, X)
app_in_aga(Ys) → U6_aga(Ys, app_in_aga(Ys))
U6_aga(Ys, app_out_aga(Xs, Ys, Zs)) → app_out_aga(., Ys, .)


s = U4_AA(Xs, app_out_gaa(X1s)) evaluates to t =U4_AA(., app_out_gaa([]))

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:



Rewriting sequence

U4_AA(Xs, app_out_gaa(X1s)) → PERM_IN_AA
with rule U4_AA(Xs', app_out_gaa(X1s')) → PERM_IN_AA at position [] and matcher [X1s' / X1s, Xs' / Xs]

PERM_IN_AA → U3_AA(app_out_aga([], ., .))
with rule PERM_IN_AA → U3_AA(app_out_aga([], ., .)) at position [] and matcher [ ]

U3_AA(app_out_aga([], ., .)) → U4_AA(., app_out_gaa([]))
with rule U3_AA(app_out_aga([], ., y1)) → U4_AA(y1, app_out_gaa([]))

Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence


All these steps are and every following step will be a correct step w.r.t to Q.